package leetcode_1100;


/**
 *@author 周杨 
 *LastStoneWeightII_1049_ 给一个数组 每次可以选择任意两个元素 这两个元素如果不相等 则留下差值 问最终如何选择可以获得最小值
 *describe:动态规划 非常好的题目
 *2019年5月24日 下午14:21
 */
public class LastStoneWeightII_1049_ {
	int [][] dp;
	public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int s:stones) sum += s;
        dp = new int[stones.length+1][sum/2+1];
        int a = help(sum/2, stones, stones.length);
        return sum-2*a;
    }
	
	// 0-i 数组有效的最优解
	// w是当前的最优和 目的是寻找出两个subset和最相近
    private int help(int w, int[] s, int i){
        if(i==0) return 0;
        if(dp[i][w]!=0) return dp[i][w];
        if(s[i-1]>w){ //如果当前这个元素比w大 那么那么在其左边寻找比s[i-1]小的组合
            dp[i][w] = help(w, s, i-1);
            return dp[i][w];
        }
        else{//如果这个元素比w小 
            dp[i][w] = Math.max(s[i-1]+help(w-s[i-1], s, i-1),help(w, s, i-1));
            return dp[i][w];
        }
    }
}
